﻿// 0827train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <deque>
#include <unordered_map>

using namespace std;

/*
 小明和朋友玩跳格子游戏，有 n 个连续格子，每个格子有不同的分数
 小朋友可以选择以任意格子起跳，但是不能跳连续的格子，也不能回头跳
给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数

输入描述
给定一个数列，如: 1 2 3 1

输出描述
输出能够得到的最高分，如: 4

示例1
1 2 3 1
输出
4

选择跳第一个格子和第三个格子
 */

class Solution01
{
public:
    Solution01(vector<int>&nums)
    {
        if (nums.size()==1)
        {
            cout << nums[0];
            return;
        }

        int dp_size = nums.size()+1;
        vector<int>dynamic_vec(dp_size);

        //dp[i] 前i个数中能取到的最大
        //转移方程1不打劫i 打劫i dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])

        dynamic_vec[0] = 0;
        dynamic_vec[1] = nums[0];

        for (int i=2; i<dp_size; i++)
        {
            dynamic_vec[i] = max(dynamic_vec[i - 1], dynamic_vec[i - 2] + nums[i - 1]);
        }

        cout << dynamic_vec[nums.size()];
        //Solution01
    }
private:
};

/*
小明和朋友玩跳格子游戏，有 n 个连续格子组成的圆圈，
每个格子有不同的分数，小朋友可以选择从任意格子起跳，
但是不能跳连续的格子，不能回头跳，也不能超过一圈；
给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。
输入
给定一个数例，第一个格子和最后一个格子首尾相连，如： 2 3 2。
输出
输出能够得到的最高分，如： 3

输入
2 3 2
输出
3

输入
1 2 3 1
输出
4
 */
class Solution02
{
public:
    int computedMax(vector<int>& nums)
    {
        int dp_size = nums.size() + 1;
        vector<int>dynamic_vec(dp_size);
        //dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])

        dynamic_vec[0] = 0;
        dynamic_vec[1] = nums[0];

        for (int i=2; i<dp_size; i++)
        {
            dynamic_vec[i] = max(dynamic_vec[i - 1], dynamic_vec[i - 2] + nums[i - 1]);
        }

        return dynamic_vec[nums.size()];

        //computedMax
    }

    Solution02(vector<int>&nums)
    {
        vector<int>head_nums(nums.begin() + 1, nums.end());
        vector<int>tail_nums(nums.begin(), nums.end()-1);

        int max_head = computedMax(head_nums);
        int max_tail = computedMax(tail_nums);

        cout << max(max_head, max_tail);
        //Solution02
    }
};


/*
 比如，score[]=[1,-1,-6,7,-17,7]，
 从起点score[0]开始，
 每次最大跳的步长为k，请你返回小明跳到终点score[n-1]时，能得到的最大得分
注:
- 格子的总长度和步长的区间在[1，100000]
- 每个格子的分数在[-10000，10000]区间中;

输入描述
第一行输入总的格子数量n
第二行输入每个格子的分数score[]
第三行输入最大跳的步长k

输出描述
输出最大得分数

输入
6
1 -1 -6 7 -17 7
2
输出
14

小明从起点score[0]开始跳，第一次跳score[1]，第二次跳到score[3]，第三次跳到score[5]
因此得到的最大的得分是score[0]+ score[1]+ score[3]+ score[5]= 14
 */

class Solution03
{
public:
    Solution03(vector<int>&nums, int step)
    {
        //dp[i] i位置的最大分数
        //dp[i]=max(dp[i], dp[prev]+nums[i]
        int dp_size = nums.size();
        vector<int>dynamic_vec(dp_size, INT_MIN);

        dynamic_vec[0] = nums[0];

        for (int i=1; i<dp_size; i++)
        {
            int start = max(0, i - step);
            for (int prev=start; prev<i; prev++)
            {
                dynamic_vec[i] = max(dynamic_vec[i], dynamic_vec[prev] + nums[i]);
	            
            }
        }

        //for (auto&num:dynamic_vec)
        //{
        //    cout << num << ' ';
        //}

        //求跳到最后的最大分
        cout << dynamic_vec[dp_size - 1];

        //Solution03
    }
};


/*
4种售票方式，分别为一日票（1天）、三日票（3天）、周票（7天）和月票（30天）
times = [1,3,7,30]
每种售票方式的价格将由一个数组给出，每种票据在票面时限内可以无限制的进行游玩
例如，小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制的游玩

小王计划在接下来一年内多次游玩该游乐园
小王计划的游玩日期将由一个数组给出
根据售票价格数组, 小王计划游玩日期数组，返回完成游玩计划所需要的最低消费

输入描述
输入为 2 个数组：
售票价格数组为 costs，costs.length = 4，默认顺序为一日票、三日票、周票和月票
小王计划游玩日期数组为 days，1 ≤ days.length ≤ 365，1 ≤ days[i] ≤ 365，默认顺序为升序

输出描述
完成游玩计划的最低消费

输入
5 14 30 100
1 3 5 20 21 200 202 230
输出
40
根据售票价格数组和游玩日期数组给出的信息，发现每次去玩的时候买一张一日票是最省钱的，
所以小王会卖 8 张一日票，每张 5 元，最低花费是 40 元

输入
一日票 三日票 周票 月票
5 14 30 100
 */

class Solution04
{
public:
    void getCostsMap(vector<int>& costs)
    {
	    //1 3 7 30
        int vec_size = costs.size();
        for (int i=0; i<vec_size; i++)
        {
            costs_map[diff_layer[i]] = costs[i];
        }

        //getCostsMap
    }

    int computedMin(vector<int>&dynamic_vec, vector<int>&nums, int curr, int prev)
    {
        int curr_diff = nums[curr] - nums[prev] + 1;

        int layer = 0;
        for (int i=0; i<diff_layer.size(); i++)
        {
	        if (curr_diff <=diff_layer[i])
	        {
                layer = diff_layer[i];
                break;
	        }
        }

        int sinle_costs = costs_map.at(1) + dynamic_vec[curr - 1];
        int layer_costs = INT_MAX;
        if (layer!=0)
        {
            layer_costs = costs_map.at(layer);
            if (prev-1>=0)
            {
                layer_costs += dynamic_vec[prev - 1];
            }
        }

        return min(sinle_costs, layer_costs);
    }

    Solution04(vector<int>&costs, vector<int>&nums)
    {
        getCostsMap(costs);
        //dp[i] 第i日最少花费
        //转移方程 i可以由i-time转移而来，直接塞一个数组，取最小值
        int dp_size = nums.size();
        vector<int>dynamic_vec(dp_size, INT_MAX);
        dynamic_vec[0] = costs_map.at(1);

        for (int i=1; i<dp_size; i++)
        {
            for (int prev=0; prev<i; prev++)
            {
                dynamic_vec[i] = min(dynamic_vec[i], computedMin(dynamic_vec, nums, i, prev));
            }
        }

        cout << dynamic_vec[dp_size - 1];
        //Solution04
    }
private:
    vector<int>diff_layer = { 1,3,7,30 };
    unordered_map<int, int>costs_map;
};


int main()
{
	{
/*
5 14 30 100
1 3 5 20 21 200 202 230
*/
        string costs_input = "5 14 30 100";
        string day_input = "1 3 5 20 21 200 202 230";
        //string costs_input;
        //string day_input;
        //getline(cin, costs_input);
        //getline(cin, day_input);

        stringstream costs_sstream(costs_input);
        stringstream day_sstream(day_input);
        string token;

        vector<int>costs_vec;
        vector<int>day_vec;

        while (costs_sstream>>token)
        {
            costs_vec.push_back(stoi(token));
        }

        while (day_sstream >> token)
        {
            day_vec.push_back(stoi(token));
        }

        Solution04 solu(costs_vec, day_vec);

        return 0;
	}
	{
/*
6
1 -1 -6 7 -17 7
2
*/
        int vec_size;
        cin >> vec_size;
        //int vec_size = 6;
        //string input = "1 -1 -6 7 -17 7";
        //stringstream oh_sstream(input);
        vector<int>nums(vec_size);

        for (int i=0; i<vec_size; i++)
        {
            //string token;
            //oh_sstream >> token;
            //nums[i] = stoi(token);
            cin >> nums[i];
        }

        //int step = 2;
        int step;
        cin >> step;

        Solution03 solu(nums, step);

        return 0;
	}
	{
        vector<int>nums;
        //string input = "1 2 3 1";
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;

        while (oh_sstream>>token)
        {
            nums.push_back(stoi(token));
        }

        Solution02 solu(nums);

        return 0;
	}
    //1 2 3 1
    //4
    vector<int>nums;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream>>token)
    {
        nums.push_back(stoi(token));
    }
    
    Solution01 solu(nums);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
